package com.yangzhe.algorithm.c036;

// 求二叉树的最大、最小深度
public class Code04_DepthOfBinaryTree_LeetCode {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    // 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    // 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 叶子节点返回1
        if (root.left == null && root.right == null) {
            return 1;
        }

        // 取巧，min的时候Integer最大值被排除掉了，如果子节点为空，则这个分支直接不参与计算了
        int leftDepth = Integer.MAX_VALUE;
        if (root.left != null) {
            leftDepth = minDepth(root.left);
        }

        int rightDepth = Integer.MAX_VALUE;
        if (root.right != null) {
            rightDepth = minDepth(root.right);
        }

        return Math.min(leftDepth, rightDepth) + 1;
    }

}
